package LearnDataStructure.b_散列结构.应用ConsistentHashing服务器集群;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-06 16:26
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.b_散列结构.应用ConsistentHashing服务器集群
 */

import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 基础实现
 * 不考虑数据倾斜
 */
public class ConsistentHashingBasic {
    private List<ConsistentHashNodeIMPL> nodes = null;
    private TreeMap<Long, ConsistentHashNodeIMPL> hashAndNode = new TreeMap<>();//保存所有机器节点在环上的位置(hash值)的容器
    private TreeMap<Long, ConsistentHashNodeIMPL> keyAndNode = new TreeMap<>();//保存所有请求(hash值)归属于哪个机器节点的容器

    public ConsistentHashingBasic(List<ConsistentHashNodeIMPL> nodes) {
        this.nodes = nodes;
        init();
    }

    public TreeMap<Long, ConsistentHashNodeIMPL> getHashAndNode() {
        return hashAndNode;
    }

    public TreeMap<Long, ConsistentHashNodeIMPL> getKeyAndNode() {
        return keyAndNode;
    }

    /**
     * 哈希算法
     * 具体的实现有些不懂
     * 将关键字映射到2^32的环状空间里面
     * MurMurHash算法，是非加密HASH算法，性能很高，
     * 比传统的CRC32,MD5，SHA-1（这两个算法都是加密HASH算法，复杂度本身就很高，带来的性能上的损害也不可避免）
     * 等HASH算法要快很多，而且据说这个算法的碰撞率很低.
     * http://murmurhash.googlepages.com/
     * @param key
     * @return
     */
    private static long hash(String key) {
        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
        final int seed = 0x1234ABCD;

        ByteOrder byteOrder = buf.order();
        buf.order(ByteOrder.LITTLE_ENDIAN);

        final long m = 0xc6a4a7935bd1e995L;
        final int r = 47;
        long h = seed ^ (buf.remaining() * m);
        long k = 0;
        while (buf.remaining() >= 8) {
            k = buf.getLong();

            k *= m;
            k ^= k >>> r;
            k *= m;

            h ^= k;
            h *= m;
        }
        if (buf.remaining() > 0) {
            ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);
            finish.put(buf).rewind();
            h ^= finish.getLong();
            h *= m;
        }

        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;

        buf.order(byteOrder);

        return Math.abs(h);
    }

    /**
     *初始化“hash值与机器节点”打包在一起的     列表的     函数
     */
    private void init() {
        for (int i = 0; i < nodes.size(); i++) {
            ConsistentHashNodeIMPL node = nodes.get(i);
            long hashResult = hash(node.getIp());
            hashAndNode.put(hashResult, node);
        }
    }

    /**
     * 添加请求的add函数
     * @param requestIp
     */
    public void addRequest(String requestIp) {
        long fromKey = hash(requestIp);
        //找到hashAndNode这个source_map中，key比fromKey大的，所有的键值对，这些键值对组成一个子Map————subMap
        SortedMap<Long, ConsistentHashNodeIMPL> subMap = hashAndNode.tailMap(fromKey);
        if (subMap.size() == 0) {//如果hashAndNode中没有大于fromKey的key，那么sybMap的元素数==0
            keyAndNode.put(fromKey, hashAndNode.firstEntry().getValue());//此时把这个请求归类到第一个机器节点；因为环状嘛，自己画图看看
        } else {//存在满足要求的机器节点targetNode，那就归属到targetNode
            ConsistentHashNodeIMPL targetNode = subMap.get(subMap.firstKey());//满足要求的机器节点可能有很多，因为环状，我们只要subMap中的第一个满足要求的机器节点
            keyAndNode.put(fromKey, targetNode);
        }
    }

    /**
     * 添加新机器节点
     * @param newNode
     */
    public void addNode(ConsistentHashNodeIMPL newNode) {
        long fromKey = hash(newNode.getIp());
        //把新机器节点存入容器
        hashAndNode.put(fromKey, newNode);
        //下面找，newNode的紧邻的上一个机器节点：
        //先生成所有key小于newNode的key的机器节点，以map的形式返回，也就是allPreNodes
        SortedMap<Long, ConsistentHashNodeIMPL> allPreNodes = hashAndNode.headMap(fromKey);
        //有可能没有机器节点的key小于fromKey
        if (allPreNodes.size() == 0) {//所以先进行判断
            /*
            此时，需要把
            newNode的紧邻的上一个机器节点(设为A)到newNode之间的
            所有的请求的归属节点更改为newNode
            这个范围包括
            [A.hash值,(2^32)-1]
            [0,newNode.hash值]
            因为我们的数据结构在逻辑上是个环
            我们规定了这个环有这样的规则： (2^32)-1    +    1    =    0
             */
            //先处理[0,newNode.hash值]
            //寻找在这个[0,newNode.hash值]区间的所有的请求；以map形式返回即between
            SortedMap<Long, ConsistentHashNodeIMPL> between = keyAndNode.subMap(0L, fromKey);
            //修改每一个请求的，归属机器节点
            for (Map.Entry<Long, ConsistentHashNodeIMPL> element : between.entrySet()) {
                element.setValue(newNode);
            }
            //处理[A.hash值,(2^32)-1]
            /*
            tailMap(hash值)方法
            其作用是，寻找所有key大于hash值的元素
                而因为我们的hash值在创造的时候有上限(2^32)-1
                所以问我们能认为，这个方法，是可以寻找[A.hash值,(2^32)-1]的所有请求的
             */
            //寻找在这个[A.hash值,(2^32)-1]区间的所有的请求；以map形式返回即between
            between = keyAndNode.tailMap(hashAndNode.lastKey());
            //修改每一个请求的，归属机器节点
            for (Map.Entry<Long, ConsistentHashNodeIMPL> element : between.entrySet()) {
                element.setValue(newNode);
            }
        } else {
            Long from = allPreNodes.lastKey();//newNode的紧邻的上一个机器节点的hash值；
            long to = fromKey;//当前newNode的哈希值
            //寻找在这个[from,to]区间的所有的请求；以map形式返回即between
            SortedMap<Long, ConsistentHashNodeIMPL> between = keyAndNode.subMap(from, to);
            //修改每一个请求的，归属机器节点
            for (Map.Entry<Long, ConsistentHashNodeIMPL> element : between.entrySet()) {
                element.setValue(newNode);
            }
        }
    }

}
